NC88 寻找第K大

https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf

当复习了一遍快排

package main

import (
    "math/rand"
    "time"
)


/**
 * 
 * @param a int整型一维数组 
 * @param n int整型 
 * @param K int整型 
 * @return int整型
*/
func findKth( a []int ,  n int ,  K int ) int {
    if (n < K || len(a) < K) {
        return -1
    }

    sort(a, 0, n - 1, n)
    return a[n - K]
}
// 随机数
var r = rand.New(rand.NewSource(time.Now().Unix()))

func sort(arr []int, start, end, n int) {
    // Base case
    if start < 0 || end > n || start >= end {return}
    
    i := start
    min := start - 1
    max := end + 1
    // 随机坑位
    num := arr[r.Intn(end-start)+start]
    for i < n && i != max {
        if arr[i] < num {
            min++
            // 只有不一样才要换
            if min != i {
                tmp := arr[min]
                arr[min] = arr[i]
                arr[i] = tmp
            }
            i++
        } else if arr[i] > num {
            max--
            if max != i {
                tmp := arr[max]
                arr[max] = arr[i]
                arr[i] = tmp
            }
        } else {
            i++
        }
    }
    
    sort(arr, start, min, n)
    sort(arr, max, end, n)
}